package ext;

import java.util.Arrays;

//航班具有开始时间和结束时间，求一个时刻最大航班数
public class MaxAirport {
    
    //仿照线段覆盖
    public int maxAirport(int[][] nums) {
        int n = nums.length;
        Node[] res = new Node[n];
        int idx = -1;
        res[++idx] = new Node(nums[0], 1);
        int ans = 1;
        Arrays.sort(nums, (n1, n2) -> {
            if (n1[0] == n2[0]) {
                return n1[1] - n2[1];
            } else {
                return n1[0] - n2[0];
            }
        });
        for (int i = 1; i < n; i++) {
            int[] cur = nums[i];
            int[] last = res[idx].arr;
            if (last[1] <= cur[0]) {
                //不重合
                res[++idx] = new Node(cur, 1);
            } else {
                int j = idx;
                while (j > 0 && res[j - 1].arr[1] > cur[0]) {
                    j--;
                }
            }
        }
        return ans;
    }

    class Node {
        int[] arr;
        int time;

        public Node(int[] arr, int time) {
            this.arr = arr;
            this.time = time;
        }
    }

}
